#include <bits/stdc++.h>
#include <iterator>
#include <sstream>
using namespace std;

// //stringstream
// string reverseWords(string s){
//     stringstream ss;
//     ss << s;
//     string str;
//     stack<string> stk;
//     while(ss >> str){
//         stk.push(str);
//     }
//     string res;
//     while(!empty(stk)){
//         res += stk.top();
//         stk.pop();
//         if(!stk.empty()) res+=' ';
//     }
//     return res;
// }

//On O1
class Solution {
public:
    void remove_blank(string& s){
        //双指针降低复杂度
        int left=0; int right=0;
        int n = s.size();
        int cnt = 0;
        //前导空格
        while(right<n && s[right]==' ') ++right;
        //尾部空格
        while(n>0 && s[n-1]==' ') --n;
        //中间空格
        while(right<n){
            while(right<n && s[right]==' ') ++right;
            while(right<n && s[right]!=' ') {s[left++] = s[right++]; ++cnt;}
            if(right<n) {s[left++] = ' '; ++cnt;}
        }
        s.resize(cnt);
        
    }
    void reversestr(string& s, int begin, int end){
        int k = end-begin;
        for(int i=0; i<(k>>1); ++i){
            swap(s[begin+i], s[end-i-1]);
        }
    }
    string reverseWords(string s) {
        //去空格
        remove_blank(s);
        //反转
        reversestr(s, 0, s.size());
        //反转单词
        int left=0; int right=0;
        while(right<s.size()){
            while(right<s.size() && s[right]!=' ') ++right;
            reversestr(s, left, right);
            ++right;
            left = right;
        }
        return s;
    }
};

int main(){
    Solution solution;
    string s = "  hello world  ";
    s = solution.reverseWords(s);
    cout<<s<<endl;
    return 0;
}